package class10;

import java.util.*;

/**
 *
 * 拓扑排序(有向无环图 DAG, 不允许循环依赖)
 * 思路:
 * 1.先找到入度为0的点
 * 2.删除入度为0的点, 再去找入度为0的点
 * 3.循环至没有入度为0的点
 *
 */
public class Code03_TopologySort {

	// directed graph and no loop
	// 返回 List<Node>, 左边是拓扑排序较小的节点(入度小)
	public static List<Node> sortedTopology(Graph graph) {
		// key：某一个node
		// value：剩余的入度
		HashMap<Node, Integer> inMap = new HashMap<>();
		// 剩余入度为0的点，才能进这个队列
		Queue<Node> zeroInQueue = new LinkedList<>();
		
		
		for (Node node : graph.nodes.values()) {
			inMap.put(node, node.in);
			if (node.in == 0) {
				zeroInQueue.add(node);
			}
		}
		// 拓扑排序的结果，依次加入result
		List<Node> result = new ArrayList<>();
		while (!zeroInQueue.isEmpty()) {
			//入度为0的节点弹出后直接加入排序结果集
			Node cur = zeroInQueue.poll();
			result.add(cur);
			//当前出队的点, 在入度映射表中, 将当前点的邻居节点的入度-1
			for (Node next : cur.nexts) {
				inMap.put(next, inMap.get(next) - 1);
				if (inMap.get(next) == 0) {
					zeroInQueue.add(next);
				}
			}
		}
		return result;
	}
}
